/* buddy.c
 *
 * Define the general data structures and algorithms 
 */
#include <types.h>
#include "panic.h"
#include "buddy.h"

void* buddy_alloc(struct buddy_class* buddy_class, uint32 size)
{
     int i;
     struct buddy_bucket* bucket = buddy_class->bucket;
     
     for (i = 0; i < buddy_class->bucket_total; ++i)
     {
	  if (size <= bucket[i].size)
	  {
	       break;
	  }
     }

     if (i == buddy_class->bucket_total)
     {
	  panic("Request alloc maximum size exceeded.");
     }

     if (bucket[i].next != NULL)
     {
	  struct buddy_slinked_list* ret = bucket[i].next;
	  bucket[i].next = ret->next;

	  return ret;
     }

     /* seem nothing available here, request from the higher */
     int higher = i + 1;
     while (higher < buddy_class->bucket_total && bucket[higher].next == NULL)
     {
	  higher++;
     }
     
     uint8* new_mem = NULL;
     uint8* new_mem_high = NULL, *new_mem_low = NULL;
     
     if (higher == buddy_class->bucket_total)
     {
	  uint32 max_size = bucket[higher - 1].size;
	  new_mem = buddy_class->top_level_alloc(max_size * 2);
	  if (new_mem == NULL)
	  {
	       panic("Request memory from higher level allocator failed.\n");
	  }
     }
     else
     {
	  /* request from the higher level bucket */
	  new_mem = (uint8*) bucket[higher].next;
	  bucket[higher].next = ((struct buddy_slinked_list*) new_mem)->next;
     }

     higher--;

     /* divide into each bucket */
     while (higher >= i)
     {
	  new_mem_low = new_mem;
	  new_mem_high = new_mem + bucket[higher].size;
	  bucket[higher].next = (struct buddy_slinked_list*)new_mem_high;
	  ((struct buddy_slinked_list*) new_mem_high)->next = NULL;

	  higher--;
     }
     
     return new_mem_low;
}

void buddy_free_s(struct buddy_class* buddy_class, void* addr, uint32 size)
{
     struct buddy_bucket* bucket = buddy_class->bucket;
     
     assert(size % 2 == 0);

     /* find the proper bucket linked list */
     uint32 bucket_entry = 0;
     for (; bucket_entry != buddy_class->bucket_total; bucket_entry++)
     {
	  if (size == bucket[bucket_entry].size)
	  {
	       break;
	  }
     }


     /* find the position of the node */
     register struct buddy_slinked_list* node = NULL, *parent = NULL;
insert:
     /* give back to the top level allocator */
     if (size == bucket[buddy_class->bucket_total - 1].size * 2)
     {
	  buddy_class->top_level_free_s(addr, size);
	  return;
     }
     
     node = bucket[bucket_entry].next;
     parent = NULL;
     /* just insert if bucket is empty */
     if (node == NULL)
     {
	  bucket[bucket_entry].next = addr;
	  ((struct buddy_slinked_list*) addr)->next = NULL;
	  return;
     }

     /* find the node and insert after it */
     while(node != NULL)
     {
	  if ((uint32) addr < (uint32) (node->next) || node->next == NULL)
	  {
	       break;
	  }
	  parent = node;
	  node = node->next;
     }

     /* insert and merge with neighbors if available */

     /* if parent == NULL, here we have 2 conditions
	1. addr should be inserted before or after the head node
	2. we only have one node in that slinked list
	
        bucket[i]->next|->|head(1)|->|2|->...
	insert in front of the head node or after the header

     */
     if (parent == NULL)
     {
	  if ((uint32)addr < (uint32)node)	/* in front of the header */
	  {
	       ((struct buddy_slinked_list*) addr)->next = bucket[bucket_entry].next;
	       bucket[bucket_entry].next = (struct buddy_slinked_list*) addr;

	       /* merge right only */

	       if ((uint32) addr + bucket[bucket_entry].size == (uint32)(((struct buddy_slinked_list*)addr)->next)) /* merge right */
	       {
		    bucket[bucket_entry].next = node->next;
		    size *= 2;
		    bucket_entry++;
		    addr = addr; /* that's right, addr enlarged */
		    goto insert;
	       }
	       return;
	  }
	  else
	  {
	       /* tricky */
	       parent = (struct buddy_slinked_list*) &bucket[bucket_entry].next;
	  }
     }
     ((struct buddy_slinked_list*) addr)->next = node->next;
     node->next = addr;

     if ((uint32) addr + bucket[bucket_entry].size ==
	 (uint32)(((struct buddy_slinked_list*) addr)->next)) /* merge right */
     {
	  node->next = ((struct buddy_slinked_list*) addr)->next->next;
	  addr = addr; 		/* just a note, leave it to compiler */
     }
     else if ((uint32) node + bucket[bucket_entry].size == (uint32)addr)
     {
	  parent->next = ((struct buddy_slinked_list*)addr)->next;
	  addr = node;
     }
     
     size *= 2;
     bucket_entry++;
     goto insert;
     
     return;
}

void buddy_bucket_dump(struct buddy_bucket* bucket, uint32 len)
{
     int i;
     for (i = 0; i < len; ++i)
     {
	  printk("size:%d||", bucket[i].size);

	  struct buddy_slinked_list* node = bucket[i].next;
	  while (node != NULL)
	  {
	       printk("0x%x|->|", node);
	       node = node->next;
	  }
	  printk("NULL\n");
     }
}
     
